Nawiasy

Limit pamięci: 32 MB

To zadanie pojawiło się równolegle na finale IX OI. Polecamy wysyłać rozwiązania do tamtego zadania, to zostanie wkrótce usunięte z serwisu.

Działanie odejmowania nie jest łączne, np. , natomiast , a zatem . Wynika stąd, że wartość wyrażenia postaci zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania w kolejności od lewej do prawej, czyli wyrażenie jest równoważne wyrażeniu .

Mamy dane wyrażenie postaci:

gdzie oznacza (plus) lub (minus), a oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:

tak rozstawić par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, chcąc uzyskać wyrażenie równoważne wyrażeniu:

możemy w:

rozmieścić nawiasy w następujący sposób:

.

Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest

• albo pojedyncza zmienna,
• albo wyrażenie postaci , w którym i , to w pełni i poprawnie ponawiasowane wyrażenia.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis danego wyrażenia postaci ,
• obliczy na ile różnych sposobów (modulo ) można rozstawić par nawiasów w wyrażeniu tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita , . Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych wierszy jest zapisany jeden znak, lub . W -tym wierszu zapisany jest znak występujący w danym wyrażeniu między a .

Wyjście

Twój program powinien zapisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitą równą ilości różnych sposobów (modulo ), na jakie można rozstawić par nawiasów w wyrażeniu tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.

Przykład

Dla danych wejściowych:

7
-
-
+
+
-
+

poprawną odpowiedzią jest:

3